package a_sorting_basic.c_insertion_sort;

import a_sorting_basic.c_insertion_sort.sorting_helper.SortingTestC;
import utils.ArrayGeneric;

// 4 - 希尔排序 Shell Sort  位置稳定 O（N^1.3）
// 也叫缩小增量排序 是插入排序的延伸 平均效率可达O（N^3/2）
// 每次和前H个数据进行比较和插入， H是一个逐渐递减到1的数列
// 从整体上使所有元素以越来越快的速度趋近于有序 - 最快速度达到宏观有序
// 虽然速度比不上NLogN的排序算法
// 但是实现更为简单
@SuppressWarnings("unchecked")
public class ShellSortC extends SortingTestC {

    @Override
    public void sort(ArrayGeneric arr) {
        int len = arr.length();
        int h = 1;

        // 根据数据规模倒推h的取值
        while (h < len / 3) {
            h = 3 * h + 1;
        }
        // increment sequence of H   -> 1,4,13,,40,121, ..
        while (h >= 1) {
            // h sort
            for (int i = h; i < len; i++) {
                // 对 下标 i, i-h, i - 2h,i - 3h.. 使用插入排序
                Comparable e = arr.get(i);
                int j;
                for (j = i; j >= h && arr.get(j - h).compareTo(e) > 0; j -= h) {
                    arr.put(j, arr.get(j - h));
                }
                arr.put(j, e);
            }
            h /= 3;
        }
    }
}
